home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 8: LINUX Games / Linux Cubed Series 8 - LINUX Games.iso / games / x11 / strategy / xsok-1.000 / xsok-1 / xsok-1.01 / solver / solve.c < prev   
C/C++ Source or Header  |  1994-11-24  |  13KB  |  578 lines
  1. #include <time.h>
  2. #include <assert.h>
  3. #include "BFS.h"
  4.  
  5. #ifdef HP
  6. #define HASHBITS 24        /* 16 M entries => 48 MB RAM */
  7. #define MEM    201326592    /* 192 MB total */
  8. #else
  9. #define HASHBITS 20        /* 1 M entries => 3 MB RAM */
  10. #define MEM    (13152*1024)    /* 14 MB total */
  11. #endif
  12.  
  13. #define MAXBOXES 32
  14. typedef unsigned char zchar;
  15. int xlevel;
  16.  
  17. void fatal(const char *msg, ...) {
  18.     va_list args;
  19.  
  20.     va_start(args, msg);
  21.     vfprintf(stderr, msg, args);
  22.     fprintf (stderr, "\n");
  23.     exit (1);
  24. }
  25.  
  26. void *malloc_(size_t n) {
  27.     void *p;
  28.     if (!n)
  29.     return NULL;    /* since malloc(0) may return NULL */
  30.     p = malloc(n);
  31.     if (!p)
  32.     fatal("out of memory");
  33.     return p;
  34. }
  35.  
  36.  
  37. /* const char *xsokdir = "/usr/games/lib/xsok/Sokoban"; */
  38. const char *xsokdir = "../lib/Sokoban";
  39. #define MAXROW    22
  40. #define MAXCOL    32
  41.  
  42. int numrows, numcols, plx, ply, orgplx, orgply;
  43. unsigned char map[MAXROW][MAXCOL], map2[MAXROW][MAXCOL], dist[MAXROW][MAXCOL];
  44.  
  45. static void dfs(int x, int y) {
  46.     if (x < 0 || y < 0 || x >= numcols || y >= numrows)
  47.     return;
  48.     if (!(map[y][x] & 4) || (map[y][x] & 0x10))
  49.     return;
  50.     map[y][x] |= 0x10;
  51.     dfs(x-1, y);
  52.     dfs(x, y-1);
  53.     dfs(x+1, y);
  54.     dfs(x, y+1);
  55. }
  56.  
  57. /* Bits in map: 0 = box there, 1 = target square, 2 = player allowed, 3 = box allowed */
  58. #define BOX    1
  59. #define TARGET    2
  60. #define MAYGO    4
  61. #define MAYBOX    8
  62. #define DONE    0x10
  63.  
  64. #define MAXILL 2000
  65. int pairs = 0;
  66. int mbx[256], mby[256];
  67. struct illegal {
  68.    int x1, y1, x2, y2;
  69. } illpairs[MAXILL];
  70.  
  71. static void add_illegal(int x1, int y1, int x2, int y2) {
  72.     int i;
  73.     struct illegal *ip;
  74.     if (pairs == MAXILL)
  75.     return;        /* cannot store more illegal pairs */
  76.     if (!(map[y1][x1] & map[y2][x2] & MAYBOX))
  77.     return;        /* cannot happen at all */
  78.     ip = illpairs;
  79.     for (i = 0; i < pairs; ++i, ++ip) {
  80.     if (ip->x1 == x1 && ip->y1 == y1 && ip->x2 == x2 && ip->y2 == y2)
  81.         return;
  82.     if (ip->x1 == x2 && ip->y1 == y2 && ip->x2 == x1 && ip->y2 == y1)
  83.         return;
  84.     }
  85.     ip->x1 = x1;
  86.     ip->y1 = y1;
  87.     ip->x2 = x2;
  88.     ip->y2 = y2;
  89.     printf("illegal pair: (%d,%d) with (%d,%d)\n", x1, y1, x2, y2);
  90.     ++pairs;
  91. }
  92.  
  93. static int check_pairs(void) {
  94.     int i;
  95.     struct illegal *ip;
  96.     ip = illpairs;
  97.     for (i = 0; i < pairs; ++i, ++ip)
  98.     if (map[ip->y1][ip->x1] & map[ip->y2][ip->x2] & BOX)
  99.         return 0;
  100.     return 1;    /* cannot see a reason to reject */
  101. }
  102.  
  103. void collect_illegal_pairs(void) {
  104.     int x, y;
  105.     for (y = 1; y < numrows-1; ++y)
  106.     for (x = 1; x < numcols-1; ++x)
  107.         if (!(map[y][x] & MAYGO)) {    /* there is a wall */
  108.         if (map[y+1][x] & MAYGO) {
  109.             if (x > 1 &&
  110.             (map[y][x-2] & MAYGO) && !(map[y+1][x-2] & MAYGO))
  111.                 add_illegal(x-1, y, x-1, y+1);
  112.             if (x < numcols-2 &&
  113.             (map[y][x+2] & MAYGO) && !(map[y+1][x+2] & MAYGO))
  114.                 add_illegal(x+1, y, x+1, y+1);
  115.         }
  116.         if (y < numcols-2 && (map[y+2][x] & MAYGO)) {
  117.             if (!(map[y+2][x-1] & MAYGO) && (map[y][x-1] & MAYGO))
  118.             add_illegal(x-1, y+1, x, y+1);
  119.             if (!(map[y+2][x+1] & MAYGO) && (map[y][x+1] & MAYGO))
  120.             add_illegal(x+1, y+1, x, y+1);
  121.         }
  122.         }
  123. }
  124.  
  125. void ParseMapFile(int level) {
  126.     FILE *fp;
  127.     int x, y;
  128.     char s[256];
  129.  
  130.     sprintf(s, "%s/screen.%02d", xsokdir, level);
  131.     if (!(fp = fopen(s, "r")))
  132.     fatal("cannot open level\n");
  133.  
  134.     memset(map, 0, sizeof(map));
  135.  
  136.     for (y = 1; fgets(s, sizeof(s), fp); ++y) {
  137.     /* parse s to map */
  138.     int c;
  139.     if (*s == ';') {
  140.         --y;
  141.         continue;
  142.     }
  143.     if (y == MAXROW-1)
  144.         fatal("Level is too big\n");
  145.     for (x = 1; (c=s[x-1]) && c != '\n'; ++x) {
  146.         if (x == MAXCOL-1)
  147.         fatal("Level is too wide\n");
  148.         if (x > numcols)
  149.         numcols = x;
  150.         switch (c) {
  151.         case '#':
  152.         map[y][x] = 0;    /* no go */
  153.         break;
  154.         case '.':
  155.         map[y][x] = 0x0f-BOX;    /* no go */
  156.         break;
  157.         case '*':
  158.         map[y][x] = 0x0f;    /* target + box! */
  159.         break;
  160.         case '$':
  161.         map[y][x] = 0x0f-TARGET;    /* no go */
  162.         break;
  163.         case '@':
  164.         orgplx = plx = x;
  165.         orgply = ply = y;
  166.         case ' ':
  167.         map[y][x] = 0x0f-TARGET-BOX;    /* player & box allowed */
  168.         break;
  169.         default:
  170.         fatal("Cannot handle character 0x%02x\n", c);
  171.         }
  172.     }
  173.     }
  174.     fclose(fp);
  175.     numrows = y+1;
  176.     numcols += 2;
  177.     /* change floor to void */
  178.     dfs(plx, ply);
  179.     for (x = 0; x < MAXCOL; ++x)
  180.     for (y = 0; y < MAXROW; ++y) {
  181.         if (!(map[y][x] & 0x10))
  182.         map[y][x] = 0;
  183.         else
  184.         map[y][x] &= 0x0f;
  185.     }
  186.     
  187. }
  188.  
  189.  
  190. void mask_map(void) {
  191.     int x, y;
  192.     for (y = 2; y < numrows-2; ++y)
  193.     for (x = 2; x < numcols-2; ++x)
  194.         if ((map[y][x] & 6) == MAYGO) { /* not dest, player allowed */
  195.         if (!(MAYGO & (map[y-1][x]|map[y][x-1])))
  196.             map[y][x] &= ~8;    /* no box allowed here */
  197.         if (!(MAYGO & (map[y+1][x]|map[y][x-1])))
  198.             map[y][x] &= ~8;    /* no box allowed here */
  199.         if (!(MAYGO & (map[y-1][x]|map[y][x+1])))
  200.             map[y][x] &= ~8;    /* no box allowed here */
  201.         if (!(MAYGO & (map[y+1][x]|map[y][x+1])))
  202.             map[y][x] &= ~8;    /* no box allowed here */
  203.         }
  204. }
  205.  
  206. void print_map(void) {
  207.     int x, y;
  208.     for (y = 1; y < numrows-1; ++y) {
  209.     for (x = 1; x < numcols-1; ++x)
  210.         if (map[y][x] & MAYBOX) {
  211.         if (map[y][x] & BOX)
  212.             putchar('$');
  213.         else
  214.             if (map[y][x] & DONE)
  215.             putchar(':');
  216.             else
  217.             putchar(' ');
  218.         } else  {
  219.         if (map[y][x] & MAYGO)
  220.             putchar('.');
  221.         else
  222.             putchar('#');
  223.         }
  224.     putchar('\n');
  225.     }
  226. }
  227. int maygo = 0, maybox = 0, boxes = 0;
  228.  
  229. void statistics(void) {
  230.     int x, y;
  231.     for (y = 1; y < numrows-1; ++y)
  232.     for (x = 1; x < numcols-1; ++x) {
  233.         if (map[y][x] & MAYBOX) {
  234.         mbx[maybox] = x;
  235.         mby[maybox] = y;
  236.         ++maybox;
  237.         } else
  238.         if (map[y][x] & MAYGO)
  239.             ++maygo;
  240.         if (map[y][x] & BOX)
  241.         ++boxes;
  242.     }
  243.     maygo += maybox;
  244.     printf("%d squares for boxes, %d boxes, %d total squares\n",
  245.        maybox, boxes, maygo);
  246.     {   double num;
  247.     num = maybox;
  248.     for (x = 2; x <= boxes; ++x) {
  249.         num *= maybox - (x-1);
  250.         num /= x;
  251.     }
  252.     printf("%e possibilities\n", num);
  253.     }
  254.     if (boxes > MAXBOXES || maybox > 256)
  255.     fatal("Level too large");
  256. }
  257. zchar bitpos[2+MAXBOXES];
  258. zchar solpos[MAXBOXES];
  259. int level = 1;
  260.  
  261. static void reset_done(void) {
  262.     int x, y;
  263.     for (y = 1; y < numrows-1; ++y)
  264.     for (x = 1; x < numcols-1; ++x)
  265.         map[y][x] &= ~DONE;
  266. }
  267.  
  268. static void pldfs(int x, int y) {
  269.     if (!(map[y][x] & MAYGO) || (map[y][x] & BOX) || (map[y][x] & DONE))
  270.     return;
  271.     map[y][x] |= DONE;
  272.     pldfs(x-1, y);
  273.     pldfs(x, y-1);
  274.     pldfs(x+1, y);
  275.     pldfs(x, y+1);
  276. }
  277.  
  278. static void norm_playerpos(void) {
  279.     int x, y;
  280.     reset_done();
  281.     pldfs(plx, ply);
  282.     for (y = 1; y < numrows-1; ++y)
  283.     for (x = 1; x < numcols-1; ++x)
  284.         if (map[y][x] & DONE) {
  285.         plx = x;
  286.         ply = y;
  287.         return;
  288.         }
  289. }
  290.  
  291. void sol_to_bits(void) {
  292.     int i, j, x, y;
  293.     j = 0;
  294.     for (i = 0; i < maybox; ++i) {
  295.     x = mbx[i];
  296.     y = mby[i];
  297.     if (map[y][x] & TARGET)
  298.         solpos[j++] = i;
  299.     }
  300.     printf("solpos has %d targets:", j);
  301.     for (i = 0; i < j; ++i)
  302.     printf(" %2d", solpos[i]);
  303.     printf("\n");
  304.     if (j != boxes)
  305.     fatal("different tnumber of targets and boxes!\n");
  306. }
  307. void pos_to_bits(void) {
  308.     int i, j, x, y;
  309.     norm_playerpos();
  310.     memset(bitpos, 0, sizeof(bitpos));
  311.     bitpos[0] = plx;
  312.     bitpos[1] = ply;
  313.     j = 2;
  314.     for (i = 0; i < maybox; ++i) {
  315.     x = mbx[i];
  316.     y = mby[i];
  317.     if (map[y][x] & BOX)
  318.         bitpos[j++] = i;
  319.     }
  320. }
  321. void bits_to_pos(void) {
  322.     int i, j, x, y;
  323.     for (y = 1; y < numrows-1; ++y)
  324.     for (x = 1; x < numcols-1; ++x)
  325.         map[y][x] &= ~BOX;
  326.     plx = bitpos[0];
  327.     ply = bitpos[1];
  328.     for (j = 2; j < boxes + 2; ++j) {
  329.     i = bitpos[j];
  330.     map[mby[i]][mbx[i]] |= BOX;
  331.     }
  332.     reset_done();
  333.     pldfs(plx, ply);
  334. }
  335.  
  336. unsigned char smap[MAXROW][MAXCOL];
  337. #if 0
  338. int best = 0;
  339. static int count_good(void) {
  340.     int x, y, good;
  341.     good = 0;
  342.     for (y = 2; y < numrows-2; ++y)
  343.     for (x = 2; x < numcols-2; ++x)
  344.         if ((map[y][x] & (BOX|TARGET)) == (BOX|TARGET))
  345.         ++good;
  346.     if (good <= best)
  347.     return good;
  348.     best = good;
  349.     printf("%d boxes good!\n", best);
  350.  
  351.     good = 0;
  352.     for (y = 2; y < numrows-2; ++y)
  353.     for (x = 2; x < numcols-2; ++x)
  354.         if ((map[y][x] & (BOX)) == (BOX))
  355.         ++good;
  356.     printf("%d boxes total!\n", good);
  357.     good = 0;
  358.     for (y = 2; y < numrows-2; ++y)
  359.     for (x = 2; x < numcols-2; ++x)
  360.         if ((map[y][x] & TARGET))
  361.         ++good;
  362.     printf("%d targets total!\n", good);
  363. }
  364. #else
  365. #define count_good()
  366. #endif
  367.  
  368. #define NOT(c)    (!(c & MAYGO) || (c & BOX))
  369.  
  370. #define TEST(dx,dy,dir)     \
  371.             if (!(map2[y+dy][x+dx]&BOX) && (map[y+dy][x+dx]&BOX)) { \
  372.                /* d+dx,y+dy is the new posn. */ \
  373.                move_player_to(x-(dx),y-(dy), fp); \
  374.                putc(dir,fp); orgplx = x; orgply=y; goto naus;}
  375.  
  376. #define STEP(dx,dy) if ((map2[y+dy][x+dx] & (MAYGO|BOX)) == MAYGO && dist[y+dy][x+dx] > d) \
  377.    (dist[remy[wr] = y+dy][remx[wr]= x+dx] = d), ++wr;
  378.  
  379. void move_player_to(int xx, int yy, FILE *fp) {
  380.     unsigned char rem[100];
  381.     int length, i;
  382.     int rd = 0, wr = 1, remx[1000], remy[1000];
  383.     memset(dist, 0xff, sizeof(dist));
  384.     dist[remy[0] = ply][remx[0] = plx] = 0;
  385.     while (rd < wr) {
  386.     int x, y, d;
  387.     x = remx[rd];
  388.     y = remy[rd++];
  389.     d = 1 + dist[y][x];
  390.     STEP(1,0);
  391.     STEP(0,1);
  392.     STEP(-1,0);
  393.     STEP(0,-1);
  394.     }
  395.     if (dist[yy][xx] == 0xff) {
  396.     fclose(fp);
  397.     fatal("ile #1\n");
  398.     }
  399.     length = dist[yy][xx];
  400.     for (i = length-1; i>= 0; --i) {
  401.          if (dist[yy-1][xx] == i) { --yy; rem[i] = 2; }
  402.     else if (dist[yy][xx-1] == i) { --xx; rem[i] = 3; }
  403.     else if (dist[yy+1][xx] == i) { ++yy; rem[i] = 0; }
  404.     else if (dist[yy][xx+1] == i) { ++xx; rem[i] = 1; }
  405.     else fatal("ile #2");
  406.     }
  407.     for (i = 0; i < length; ++i)
  408.     putc(rem[i], fp);
  409. }
  410.  
  411. void write_solution(long entrynr) {
  412.     long *positions;
  413.     char fname[100];
  414.     FILE *fp;
  415.     int i;
  416.     positions = malloc_(sizeof(long) * (level+1));
  417.     for (i = level; i >= 0; --i) {
  418.     positions[i] = entrynr;
  419.     entrynr = BFS_getentry(entrynr, bitpos);
  420.     bits_to_pos();
  421.     printf("Position after %d pushes: player at %d,%d\n", i, plx, ply);
  422.     print_map();
  423.     fflush(stdout);
  424.     if (i > 0)
  425.         assert(entrynr >= 0);
  426.     else
  427.         assert(entrynr < 0);
  428.     }
  429.     sprintf(fname, "Sokoban.%02d.sol", xlevel);
  430.     fp = fopen(fname, "wb");
  431.     /* write the "simple" magic */
  432.     putc(0, fp);
  433.     putc(0, fp);
  434.     putc(0x74, fp);
  435.     putc(0x1c, fp);
  436.     
  437.     plx = orgplx;
  438.     ply = orgply;
  439.     BFS_getentry(positions[0], &bitpos);
  440.     bits_to_pos();
  441.     for (i = 1; i <= level; ++i) {
  442.     int x, y;
  443.     memcpy(map2, map, sizeof(map));    /* the current state */
  444.     BFS_getentry(positions[i], &bitpos);
  445.     bits_to_pos();
  446.     /* make a diff map2 => map and move the player */
  447.     for (y = 2; y < numrows-2; ++y)
  448.         for (x = 2; x < numcols-2; ++x)
  449.         /* map2 is old and map is new */
  450.         if ((map2[y][x]&BOX) && !(map[y][x]&BOX)) {
  451.             /* there are 4 possibilities... (x,y) is the new player pos */
  452.             plx = orgplx;
  453.             ply = orgply;
  454.             TEST( 0,-1,0);
  455.             TEST(-1, 0,1);
  456.             TEST( 0, 1,2);
  457.             TEST( 1, 0,3);
  458.         }
  459.     fatal("ile 3");
  460.     naus:
  461.     ;
  462.     }
  463.     fclose(fp);
  464. }
  465.  
  466.  
  467. static void printtime(void) {
  468.     fflush(stdout);
  469.     system("date");
  470. }
  471.  
  472. #ifndef HP
  473. inline
  474. #endif
  475. static void try_possible_state(x, y, dx, dy) {
  476.     if (!(map[y][x] & TARGET)) {
  477.     if (!dx) {
  478.         if (NOT(map[y+dy][x]) && (
  479.                       (NOT(map[y][x-1]) && NOT(map[y+dy][x-1])) ||
  480.                       (NOT(map[y][x+1]) && NOT(map[y+dy][x+1]))
  481.                       ))
  482.         return;
  483.         /* no new forbidden square */
  484.     } else {
  485.         if (NOT(map[y][x+dx]) && (
  486.                       (NOT(map[y-1][x]) && NOT(map[y-1][x+dx])) ||
  487.                       (NOT(map[y+1][x]) && NOT(map[y+1][x+dx]))
  488.                       ))
  489.         return;
  490.         /* no new forbidden square */
  491.     }
  492.     }
  493.     if (!check_pairs())    /* is this position stuck? */
  494.     return;
  495.     pos_to_bits();
  496. #if 0
  497.     if (level < 3) {
  498.     printf("Storing new pos:\n");
  499.     print_map();
  500.     printf("%04lx %04lx\n", ((long *)bitpos)[1], ((long *)bitpos)[0]);
  501.     }
  502. #endif
  503.     if (!memcmp(solpos, bitpos+2, boxes)) {
  504.     printf("found the solution with %d pushes!\n", level);
  505.     printtime();
  506.     write_solution(BFS_store(bitpos));
  507.     exit(0);
  508.     }
  509.     count_good();
  510.     BFS_store(bitpos);
  511. }
  512.  
  513. #define TRY(dx,dy) { \
  514.     if ((map[y+dy][x+dx] & BOX) && (map[y+dy+dy][x+dx+dx] & (MAYBOX|BOX)) == MAYBOX) { \
  515.     map[y+dy][x+dx] &= ~BOX; map[y+dy+dy][x+dx+dx] |= BOX;    \
  516.         try_possible_state(x+dx+dx,y+dy+dy, dx, dy);        \
  517.        memcpy(map, smap, sizeof(map));                \
  518.     }}
  519.  
  520. static void try_all_pushes(void) {
  521.     int x, y;
  522.     memcpy(smap, map, sizeof(map));
  523.     for (y = 2; y < numrows-2; ++y)
  524.     for (x = 2; x < numcols-2; ++x)
  525.         if (map[y][x] & DONE) {
  526.         /* we may push from here */
  527.         plx = x;
  528.         ply = y;
  529.         TRY(-1,0);
  530.         TRY(1,0);
  531.         TRY(0,1);
  532.         TRY(0,-1);
  533.         }
  534. }
  535.  
  536.  
  537. int main(int argc, char *argv[]) {
  538.     size_t ndata;
  539.  
  540.     if (argc == 2)
  541.     level = atoi(argv[1]);
  542.     else
  543.     level =1;
  544.     xlevel = level;
  545.  
  546.     ParseMapFile(level);
  547.     /* mask out squares not allowed for a box */
  548.     system("uname -a");
  549.     printtime();
  550.     mask_map();
  551.     print_map();
  552.     statistics();
  553.     collect_illegal_pairs();
  554.     sol_to_bits();
  555.  
  556.     printf("mem = %ld, mem for hash = %ld\n", MEM, (3UL << HASHBITS));
  557.     ndata = (MEM - (3UL << HASHBITS)) / (boxes + 5);
  558.     if (ndata >= (3UL << (HASHBITS-2)))
  559.     ndata = (3UL << (HASHBITS-2));
  560.     printf("Using %d hashbits and %ld data entries (%d boxes)\n", HASHBITS,
  561.        ndata, boxes);
  562.     BFS_init(2 + boxes, 2 + boxes, HASHBITS, ndata, 1);    /* set keylength */
  563.     pos_to_bits();
  564.     BFS_store(bitpos);
  565.     level = 0;
  566.     while (BFS_newlevel()) {    /* there are some entries */
  567.     ++level;
  568.     /* fprintf(stderr, "searching at level %d\n", level); */
  569.     while (BFS_retrieve(bitpos)) {
  570.         bits_to_pos();
  571.         try_all_pushes();
  572.     }
  573.     }
  574.     printf("no solution found\n");
  575.     printtime();
  576.     return 0;
  577. }
  578.